МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ» Інженерно-технічний факультет Кафедра копм’ютерних систем та мереж Розрахунково-графічна робота з дисципліни «Теоретичні основи ЦОС» на тему: «Розрахунок параметрів виконання алгоритму ШПФ»  Завдання Варіант № 25 Розрахувати параметри виконання алгоритму ШПФ з такими вхідними даними: Кількість точок 16384  Основа ШПФ 4  Прорідження часове  Частота роботи процесора  1,0 МГц  Розрядність вхідних даних 16(8+8)  Тип вхідного інтерфейсу USB  Тип вихідного інтерфейсу ЦАП,8р(20 МГц)   Анотація В даній розрахунково-графічній роботі розглянуто спосіб реалізації алгоритму ШПФ за основою 4 для 16-розрядних вхідних даних з часовим прорідженням; детально описано механізми обчислення швидкого перетворення Фур’є за основою 4, обчислено часові ресурси для виконання обчислення, створена функціональна схема системи написана програма, що реалізує вказаний алгоритм ШПФ.  Зміст Вступ 5 1 Теоретичний розділ 6 1.1 Опис швидкого перетворення Фур’є з прорідженням в часі 6 2 Аналіз (розробка) блок-схеми виконання заданої функції обробки сигналів та зображень на заданому типі процесора 9 3 Розрахунковий розділ 11 4 Розробка функціональної схеми 13 5 Розробка програми виконання алгоритму ШПФ 15 Висновки 19 Література 20 Вступ Швидке перетворення Фур'є (ШПФ, FFT) - це алгоритм швидкого обчислення дискретного перетворення Фур'є (ДПФ). Тобто, алгоритм обчислення за кількість дій, менше ніж O(N2), Необхідних для прямого (за формулою) обчислення ДПФ. Іноді під БПФ розуміється один із швидких алгоритмів, званий алгоритмом проріджування по частоті / часу, що має складність O(Nlog2N). Одна з причин того, що анализ Фур’є грає важливу роль в цифровій обрабці сигналів, полягає в існуванні ефективних алгоритмів дискретного перетворення Фур’є. Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення. Крім того, ці перетворення корисні при проектуванні фільтрів. Частотна характеристика фільтра може бути отримана за допомогою перетворення Фур’є його імпульсної реакції. І навпаки, якщо визначена частотна характеристика сигналу, то необхідна імпульсна реакція може бути отримана за допомогою зворотнього перетворення Фур’є над його частотною характеристикою. Цифрові фільтри можуть бути створені на основі їхньої імпульсної реакції, оскільки коефіцієнти фільтра з кінцевою імпульсною характеристикою (КІХ) ідентичні дискретній імпульсній реакції фільтра. 1 Теоретична частина 1.1 Опис швидкого перетворення Фур’є з прорідженням в часі Дискретний матеріальний сигнал у вигляді кінцевої часової послідовності x(nТ) запишемо як x(nТ), де
- число відліків, N – число відліків, T – період дискретизації. N - точкове дискретне перетворення Фур’є (ДПФ) задається формулою:
де X(k) – частотний k-ий відлік чи k-а спектральна складова сигналу (визначає вихідну частотну послідовність, спектр сигналу),
комплексна експонента, W- ядро перетворення. При зміні значення n*k на величину кратну N ядро
не змінюється (у силу періодичності синуса і косинуса). Тобто ядро по верхньому індексу є періодичною функцією з періодом N. Тому замість добутку n*k можна вставити залишок від ділення його на N , тобто (n*k) mod N. Cпектральна функція X(k) також має період N по аргументу k. Число множень дійсних відліків сигналу на комплексне ядро в (1) дорівнює N2, а число додавань комплексних чисел – (N -1)N. Кількість цих операцій різко зростає із збільшенням N і приводить до занадто великого часу перетворення. ДПФ стало широко застосовуватися після винаходу швидких алгоритмів, в основі яких лежить принцип зведення багатоточкового перетворення до малоточкового. Один з них (що став уже класичним) називається ШПФ із проріджу-ванням за часом. Цей...